LeetCode 279、完全平方数

一、题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

二、题目解析

三、参考代码

1、Java 代码

class Solution {
    public int numSquares(int n) {


        // 设置一个数组，用来存储小于 n 的那些完全平方数
        List<Integer> square = new ArrayList<>();

        // 通过一个下标来计算
        int idx = 1;

        // 直到 idx * idx 超过了 n 为止
        while (idx * idx <= n) {
            // square 存储小于 n 的那些完全平方数
            square.add(idx * idx);

            // idx 累加
            idx++;
        }

        // dp[0] 表示数字 0  需要完全平方数的最少数量
        // dp[1] 表示数字 0  需要完全平方数的最少数量
        // dp[i] 表示数字 i  需要完全平方数的最少数量
        int[] dp = new int[ n + 1 ];

        // 先让 dp 初始化为 -1，代表 dp[i] 还没有计算
        Arrays.fill(dp,-1);

        // dp[0] 表示数字 0  需要完全平方数的最少数量
        dp[0] = 0;
        
        // 开始填充 dp[]
        for(int i = 1 ; i <= n ;i++){
            
            // 在每次填充的过程中，都去遍历 square 数组
            for(int j = 0 ;j < square.size();j++){
                // 如果发现此时 square 的元素值大于了 i
                // 那么 square 后面的那些元素没有必要参与进来计算 i 了
                // 直接退出当前的 j 的循环判断，让 i++
                if(square.get(j) > i){
                    break;
                }

                // 否则，如果 dp[i] 还没有找到数字 i 需要完全平方数的最少数量
                // 或者此时计算的新值更小，那么更新 dp[i]
                if(dp[i] == -1 || dp[i] > dp[i-square.get(j)] + 1){

                    // 更新 dp[i]
                    // dp[i] 表示数字 i  需要完全平方数的最少数量
                    // 这个时候 dp[i] 为获取数字为 square.get(j) 的那 1 个完全平方数
                    // 加上获取数字为 i-square.get(j) 最少需要 dp[i-square.get(j)] 个数
                    dp[i] = dp[i-square.get(j)] + 1;
                }
            }
        }

        // dp[n] 表示数字 n 需要完全平方数的最少数量
        // 返回这个结果就行
        return dp[n];

    }
}

**2、**C++ 代码

class Solution {
public:
    int numSquares(int n) {
        // 设置一个数组，用来存储小于 n 的那些完全平方数
        vector<int> square;

        // 通过一个下标来计算
        int idx = 1;

        // 直到 idx * idx 超过了 n 为止
        while (idx * idx <= n) {
            // square 存储小于 n 的那些完全平方数
            square.push_back(idx * idx);

            // idx 累加
            idx++;
        }

        // dp[0] 表示数字 0  需要完全平方数的最少数量
        // dp[1] 表示数字 0  需要完全平方数的最少数量
        // dp[i] 表示数字 i  需要完全平方数的最少数量
        // 先让 dp 初始化为 -1，代表 dp[i] 还没有计算
        vector<int> dp(n + 1,-1);

        // dp[0] 表示数字 0  需要完全平方数的最少数量
        dp[0] = 0;
        
        // 开始填充 dp[]
        for(int i = 1 ; i <= n ;i++){
            
            // 在每次填充的过程中，都去遍历 square 数组
            for(int j = 0 ;j < square.size();j++){
                // 如果发现此时 square 的元素值大于了 i
                // 那么 square 后面的那些元素没有必要参与进来计算 i 了
                // 直接退出当前的 j 的循环判断，让 i++
                if(square[j] > i){
                    break;
                }

                // 否则，如果 dp[i] 还没有找到数字 i 需要完全平方数的最少数量
                // 或者此时计算的新值更小，那么更新 dp[i]
                if(dp[i] == -1 || dp[i] > dp[i-square[j]] + 1){

                    // 更新 dp[i]
                    // dp[i] 表示数字 i  需要完全平方数的最少数量
                    // 这个时候 dp[i] 为获取数字为 square.get(j) 的那 1 个完全平方数
                    // 加上获取数字为 i-square.get(j) 最少需要 dp[i-square.get(j)] 个数
                    dp[i] = dp[i-square[j]] + 1;
                }
            }
        }

        // dp[n] 表示数字 n 需要完全平方数的最少数量
        // 返回这个结果就行
        return dp[n];
    }
};

3、Python 代码

class Solution:
    def numSquares(self, n: int) -> int:
        # 设置一个数组，用来存储小于 n 的那些完全平方数
        square = []

        # 通过一个下标来计算
        idx = 1

        # 直到 idx * idx 超过了 n 为止
        while idx * idx <= n : 
            # square 存储小于 n 的那些完全平方数
            square.append(idx * idx)

            # idx 累加
            idx+= 1
    

        # dp[0] 表示数字 0  需要完全平方数的最少数量
        # dp[1] 表示数字 0  需要完全平方数的最少数量
        # dp[i] 表示数字 i  需要完全平方数的最少数量
        # 先让 dp 初始化为 -1，代表 dp[i] 还没有计算
        dp = [-1 for _ in range( n + 1 )]

        # dp[0] 表示数字 0  需要完全平方数的最少数量
        dp[0] = 0
        
        # 开始填充 dp[]
        for i in range( 1 , n + 1 ) : 
            
            # 在每次填充的过程中，都去遍历 square 数组
            for j in range( 0 ,len(square) ) :  
                # 如果发现此时 square 的元素值大于了 i
                # 那么 square 后面的那些元素没有必要参与进来计算 i 了
                # 直接退出当前的 j 的循环判断，让 i++
                if square[j] > i: 
                    break
                

                # 否则，如果 dp[i] 还没有找到数字 i 需要完全平方数的最少数量
                # 或者此时计算的新值更小，那么更新 dp[i]
                if dp[i] == -1 or dp[i] > dp[i-square[j]] + 1 : 

                    # 更新 dp[i]
                    # dp[i] 表示数字 i  需要完全平方数的最少数量
                    # 这个时候 dp[i] 为获取数字为 square.get(j) 的那 1 个完全平方数
                    # 加上获取数字为 i-square.get(j) 最少需要 dp[i-square.get(j)] 个数
                    dp[i] = dp[i-square[j]] + 1
      

        # dp[n] 表示数字 n 需要完全平方数的最少数量
        # 返回这个结果就行
        return dp[n]